package leetcode;

/**
 * 227. 基本计算器 II
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 * 整数除法仅保留整数部分。
 * 示例 1：
 * 输入：s = "3+2*2"
 * 输出：7
 * 示例 2：
 * 输入：s = " 3/2 "
 * 输出：1
 * 示例 3：
 * 输入：s = " 3+5 / 2 "
 * 输出：5
 * 提示：
 * 1 <= s.length <= 3 * 105
 * s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
 * s 表示一个 有效表达式
 * 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
 * 题目数据保证答案是一个 32-bit 整数
 */

import java.util.Deque;
import java.util.concurrent.LinkedBlockingDeque;

public class problems_227 {

    public static void main(String[] args) {
        System.out.println(new Solution().calculate(" 3+5 / 2 "));
    }

    static class Solution {
        public int calculate(String s) {
            if (null == s || s.isEmpty()) return 0;
            // 去除空格
            s = s.replaceAll(" ", "");
            // 数字
            Deque<Integer> numDeque = new LinkedBlockingDeque<>();
            //
            char preSign = '+'; // 前置符号
            for (int i = 0; i < s.length(); i++) {
                // 取得当前数字
                int initIndex = i;
                // 数字时
                int temp = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    temp = temp * 10 + (s.charAt(i) - '0');
                    i++;
                }
                // 不是数字起始时，跳过
                if (i == initIndex) {
                    continue;
                }
                //
                switch (preSign) {
                    case '+':
                        numDeque.push(temp);
                        break;
                    case '-':
                        numDeque.push(-temp);
                        break;
                    case '*':
                        numDeque.push(numDeque.pop() * temp);
                        break;
                    case '/':
                        numDeque.push(numDeque.pop() / temp);
                        break;
                    default:
                }
                if (i < s.length()){
                    preSign = s.charAt(i);
                }
            }
            //
            int value = 0;
            while (!numDeque.isEmpty()){
                value += numDeque.pop();
            }
            return value;
        }
    }
}